﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Demo.Mmose.Core.Common.Sort
{
    #region zh-CHS 枚举 | en Enum
    /// <summary>
    /// 排序的方式
    /// </summary>
    public enum SortType
    {
        SmallToBig = 0x01,
        BigToSmall = 0x02,
    }
    #endregion

    /// <summary>
    /// 基数排序
    /// </summary>
    public class RadixSorter
    {
        #region zh-CHS 私有常量 | en Private Constants
        /// <summary>
        /// 
        /// </summary>
        private const int SORT_CAPACITY = 1024; // 默认的容量
        #endregion

        #region zh-CHS 私有静态方法 | en Private Static Methods
        /// <summary>
        /// 获取最大元素的位数
        /// </summary>
        /// <typeparam name="SortT"></typeparam>
        /// <param name="arraySort"></param>
        /// <param name="selector"></param>
        /// <returns></returns>
        private static int GetMaxLength<SortT>( IEnumerable<SortT> arraySort, Func<SortT, int> selector )
        {
            int iMaxNumber = arraySort.Max( selector );
            int iMinNumber = arraySort.Min( selector );

            string strMaxNumber = iMaxNumber.ToString();
            if ( iMinNumber >= 0 )
                return strMaxNumber.Length;    // 这样获得最大元素的位数是不是有点投机取巧了...

            // iMinNumber 是 负数
            string strMinNumber = iMinNumber.ToString();
            int iMinNumberLength = strMinNumber.Length - 1; // 去掉 (-) 字符

            if ( strMaxNumber.Length >= iMinNumberLength )
                return strMaxNumber.Length;
            else
                return iMinNumberLength;
        }


        /// <summary>
        /// 基数排序
        /// </summary>
        /// <param name="arraySort"></param>
        /// <param name="iMaxLength"></param>
        private static SortT[] Sort<SortT>( IEnumerable<SortT> arraySort, int iMaxLength, SortType sortType, Func<SortT, int> selector )
        {
            List<SortT> list = new List<SortT>( SORT_CAPACITY );                        // 存放每次排序后的元素

            List<SortT>[] plusListArray = new List<SortT>[10];                      // 正数 十个桶
            for ( int iIndex = 0; iIndex < plusListArray.Length; iIndex++ )         // 给十个桶分配内存初始化。
                plusListArray[iIndex] = new List<SortT>( SORT_CAPACITY );

            List<SortT>[] minusListArray = new List<SortT>[10];                     // 负数 十个桶
            for ( int iIndex = 0; iIndex < minusListArray.Length; iIndex++ )        // 给十个桶分配内存初始化。
                minusListArray[iIndex] = new List<SortT>( SORT_CAPACITY );

            for ( int iIndex = 0; iIndex < iMaxLength; iIndex++ )                   // 一共执行iMaxLength次，iMaxLength是元素的最大位数。
            {
                foreach ( var itemSort in arraySort )                               // 分桶
                {
                    // 获取比较的值
                    int iNumber = selector( itemSort );

                    // 从个位向高位开始分桶
                    int iValue = ( iNumber / (int)Math.Pow( 10.0, iIndex + 1.0 ) ) % 10;

                    // 通过iValue的值，确定它压人哪个桶中。
                    if ( iNumber >= 0 )
                        plusListArray[iValue].Add( itemSort );      // 是 正数
                    else
                    {
                        iValue = Math.Abs( iValue );
                        minusListArray[iValue].Add( itemSort );     // 是 负数
                    }
                }

                list.Clear();                                       // 清空list 准备添加

                if ( sortType == SortType.SmallToBig )
                {
                    // 从小到大
                    for ( int jIndex = minusListArray.Length - 1; jIndex >= 0; jIndex-- )  // 将十个桶里的数据重新排列，压入list
                    {
                        foreach ( var itemSort in minusListArray[jIndex].ToArray<SortT>() )
                            list.Add( itemSort );

                        minusListArray[jIndex].Clear();                    // 清空每个桶
                    }

                    for ( int jIndex = 0; jIndex < plusListArray.Length; jIndex++ )       // 将十个桶里的数据重新排列，压入list
                    {
                        foreach ( var itemSort in plusListArray[jIndex].ToArray<SortT>() )
                            list.Add( itemSort );

                        plusListArray[jIndex].Clear();                    // 清空每个桶
                    }
                }
                else
                {
                    // 从大到小
                    for ( int jIndex = plusListArray.Length - 1; jIndex >= 0; jIndex-- )  // 将十个桶里的数据重新排列，压入list
                    {
                        foreach ( var itemSort in plusListArray[jIndex].ToArray<SortT>() )
                            list.Add( itemSort );

                        plusListArray[jIndex].Clear();                    // 清空每个桶
                    }

                    for ( int jIndex = 0; jIndex < minusListArray.Length; jIndex++ )       // 将十个桶里的数据重新排列，压入list
                    {
                        foreach ( var itemSort in minusListArray[jIndex].ToArray<SortT>() )
                            list.Add( itemSort );

                        minusListArray[jIndex].Clear();             // 清空每个桶
                    }
                }

                arraySort = list.ToArray<SortT>();                  // arraySort指向重新排列的元素
            }

            return list.ToArray<SortT>();
        }
        #endregion

        #region zh-CHS 共有静态方法 | en Public Static Methods
        /// <summary>
        /// 基数排序
        /// </summary>
        /// <param name="arraySort"></param>
        public static SortT[] Sort<SortT>( IEnumerable<SortT> arraySort, SortType sortType, Func<SortT, int> selector )
        {
            int iMaxLength = GetMaxLength( arraySort, selector );

            return Sort<SortT>( arraySort, iMaxLength, sortType, selector );
        }
        #endregion
    }
}
